public class code1 {

//    没有重复项数字的全排列
//    这里使用交换、递归的形式解决

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        // 首先将 num 数组进行简单的升序排列
        // Arrays.sort(num);
        // 创建出两个顺序表
        // 首先，创建出第一个表 用来存放创建出来的各种排列情况的数组
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        // 再创建出一个顺序表，用于存储每次出现的排列情况
        ArrayList<Integer> nums = new ArrayList<>();
        // 通过循环将数组存入到 nums 表中
        for(int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }

        // 实现一个方法来将出现的排列情况存储到 res 中
        input(res, nums, 0);

        return res;
    }

    // 这里需要传入的元素包含 第一个 res 表、第二个 nums 表、以及一个记录次数的 flag 标记
    private void input(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> nums, int flag) {
        // 当这个标志 flag == nums 的长度时，此时表示 已经针对这个长度的数组找到了一种排列情况
        if(flag == nums.size() - 1) {
            // 这里将出现的一种排列情况进行添加
            res.add(nums);
        } else {
            // 这里使用一个 for 循环，将当前 nums 中的元素一一遍历
            for(int j = flag; j < nums.size(); j++) {
                // 实现一个交换函数，将指向两个位置的数字进行交换
                swap(nums, j, flag);

                // 在一次交换后，再次调用 input 函数
                // 不断向后移动，寻找后续的元素进行交换
                // 这里的标志位要 + 1 操作，就是为了让后面的 for 循环将每一个元素都进行一次操作
                input(res, nums, flag+1);

                // 之后，要防止出现 元素少判断的情况，需要进行 回溯(再次交换) 的操作
                // 比如 1234，当 交换为 3214 之后再次进行交换 出现 3412
                // 此时就会少出现一种情况 即 1432 这里就需要将第一次交换后再还原回去处理这种情况
                swap(nums, j, flag);
            }

        }
    }

    // 这里实现一个交换函数
    private void swap(ArrayList<Integer> nums, int a, int b) {
        int temp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, temp);
    }
}
